package demo.ybt;

public class P1259 {
    public static void main(String[] args) {
        P1259 p1259= new P1259();
        int res = p1259.res(new int[]{13, 7, 9, 16, 38, 24, 37, 18, 44, 19, 21, 22, 63, 15});
        System.out.println(res);
    }
    public int res(int[] t) {

        //dp[i] 代表当前位置的  最长不下降序列
        //13 7 9 16 38 24 37 18 44 19 21 22 63 15
        //
        int dp[] = new int[t.length];
        for (int i = 0; i < t.length; i++) {
            //当前自己至少连续1次
            dp[i] = 1;
        }

        //dp[0]=1
        //dp[1]=1
        //dp[2]=2 因为t[2]>=t[1] 所以把长度扩大到了7、9
        //dp[3]=3 因为t[3]>=t[2] 所以把长度扩大到了7、9、16
        //方程式就是  当t[j] <t[i] 其中j<i，那么dp[i]= dp[j]+1
        //因为j是代表i之前所有t的元素，又需要求最长，是不是就是Max(dp[j]+1)

        int max = 1;
        for (int i = 0; i < t.length; i++) {
            for (int j = 0; j < i; j++) {

                if (t[j] < t[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                    max = Math.max(dp[i], max);
                }
            }
        }

        return max;
    }
}
